//
// Created by Lenovo on 2024/3/7.
//
#include<bits/stdc++.h>
using namespace std;
//岛屿的周长
class Solution {
public:
    int row,col;
    int length=0;
    vector<vector<bool>> visited;
    int go[4][2]={{0,1,},{0,-1},{-1,0},{1,0}};

    void bfs(int x,int y,vector<vector<int>>& grid){
        queue<pair<int,int>> que;
        que.push({x,y});
        visited[x][y]=true;
        while(!que.empty()){
            pair<int, int> point = que.front();que.pop();
            int curx=point.first;
            int cury=point.second;
            //搜索相邻的格子
            for(int i=0;i<4;i++){
                int nextx=curx+go[i][0];
                int nexty=cury+go[i][1];
                //未访问的陆地，加入队列
                if(nextx>=0 && nextx<row && nexty>=0 && nexty<col
                && !visited[nextx][nexty] && grid[nextx][nexty]==1){
                    visited[nextx][nexty]=true;
                    que.push({nextx,nexty});

                }
                //边界或者是水域，周长++
                if(nextx==-1 || nextx==row || nexty==-1 || nexty==col) length++;
                if(nextx>=0 && nextx<row && nexty>=0 && nexty<col && grid[nextx][nexty]==0) length++;
            }
        }
    }


    int islandPerimeter(vector<vector<int>>& grid) {
        row=grid.size();
        col=grid[0].size();
        visited=vector<vector<bool>>(row,vector<bool>(col, false));
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(!visited[i][j] && grid[i][j]==1){
                    bfs(i,j,grid);
                }
            }
        }
        return length;
    }
};